/*
 * @Author: szx
 * @Date: 2022-01-30 13:20:58
 * @LastEditTime: 2022-04-12 14:05:03
 * @Description:
 * @FilePath: \leetcode\1-99\42\42.js
 */
/**
 * @param {number[]} height
 * @return {number}
 */
var trap = function (height) {
    //动态规划法
    if (height.length < 2) return 0;
    const n = height.length;
    const maxLeft = new Array(n).fill(0);
    maxLeft[0] = height[0];
    const maxRight = new Array(n).fill(0);
    maxRight[n - 1] = height[n - 1];
    for (let i = 1; i < n; i++) {
        maxLeft[i] = max(height[i], maxLeft[i - 1]);
        maxRight[n - i - 1] = max(height[n - i - 1], maxLeft[n - i]);
    }
    let res = 0;
    for (let i = 1; i < n - 1; i++) {
        const count = Math.min(maxLeft[i], maxRight[i]) - height;
        if (count > 0) res += count;
    }
    return res;
};

var trap = function (height) {
    //单调栈，单调递减的，遇到右边比他大高的，就弹出来
    if (height.length < 2) return 0;
    const n = height.length;
    let res = 0;
    const st = [0];
    for (let i = 1; i < n; i++) {
        while (st.length && height[i] > height[st[st.length - 1]]) {
            const mid = st.pop();
            if (st.length) {
                const h = Math.min(height[st[st.length - 1]], height[i]) - height[mid];
                const w = i - st[st.length - 1] - 1;
                res += h * w;
            }
        }
        st.push(i);
    }
    return res;
};
